/* -----------------------------------------------
 *       Filename:  rect.c
 *         Author:  MIEN
 *    Description:  矩形hash表
 *           Date:  2016-11-22
 * -----------------------------------------------
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "rect.h"

/**
 * 实现矩形 hash 表，是为了合理使用内存。
 * 即使桶值很大，也不必一次性地在内存中连续申请所有节点，
 * 只是在某一行中有数据落入的时候，才申请这一行的节点。
 * 
 * TODO: enlarge the table capacity when used > cols * rows
 */

static uint _rect_default_hash(rect_key_t key)
{
    return key.ord;
}

static int _rect_default_compare(rect_key_t key1, rect_key_t key2)
{
    if (key1.ord < key2.ord)
        return -1;
    if (key1.ord == key2.ord)
        return 0;
    return 1;
}

static void _rect_default_free (void *val)
{
    free(val);
}

rect_table_t *rect_create()
{
    return rect_create_with_size(RECT_DEFAULT_COLS, RECT_DEFAULT_ROWS);
}

rect_table_t *rect_create_with_size(int cols, int rows)
{
    rect_table_t *rt = malloc(sizeof(rect_table_t));

    if (cols < 8) cols = 8;
    if (rows < 1) rows = 1;

    rt->cols = cols;
    rt->rows = rows;
    rt->used = 0;

    rt->hash = _rect_default_hash;
    rt->free = _rect_default_free;
    rt->compare = _rect_default_compare;
 
    rt->ht = calloc(rows, sizeof(rect_node_t**));
    return rt;
}

void rect_free(rect_table_t *rt)
{
    int i, j;
    rect_node_t *t, *n;
    for (i = 0; i < rt->rows; i++) {
        if (rt->ht[i] == NULL)
            continue;
        for (j = 0; j < rt->cols; j++) {
            n = rt->ht[i][j];
            while (n != NULL) {
                t = n;
                n = n->next;
                if (rt->free != NULL & t->val != NULL) {
                    rt->free(t->val);
                }
                free(t);
            }
        }
        free(rt->ht[i]);
    }
    free(rt->ht);
    free(rt);
}

#define CALC_POSITION(r, k) \
        uint hash = (r)->hash(k); \
        int col = hash % (r)->cols; \
        int row = (hash / (r)->cols) % (r)->rows;

void *rect_get(rect_table_t *rt, rect_key_t key)
{
    CALC_POSITION(rt, key);

    if (rt->ht[row] == NULL)
        return NULL;

    rect_node_t *n = rt->ht[row][col];
    while (n != NULL) {
        if (rt->compare(n->key, key) == 0)
            return n->val;
        n = n->next;
    }
    return NULL;
}

void rect_set(rect_table_t *rt, rect_key_t key, void *val)
{
    CALC_POSITION(rt, key);

    rect_node_t *prev = NULL;
    if (rt->ht[row] != NULL && rt->ht[row][col] != NULL) {
        rect_node_t *n = rt->ht[row][col];
        while (n != NULL) {
            if (rt->compare(n->key, key) == 0){
                if (rt->free != NULL && n->val != NULL) {
                    rt->free(n->val);
                }
                n->val = val;
                return;
            }
            prev = n;
            n = n->next;
        }
    }

    rect_node_t *node = malloc(sizeof(rect_node_t));
    node->key = key;
    node->val = val;
    node->next = NULL;

    rt->used++;

    if (prev != NULL) {
        prev->next = node;
        return;
    }

    if (rt->ht[row] == NULL) {
        rt->ht[row] = calloc(rt->cols, sizeof(rect_node_t*));
    }
    rt->ht[row][col] = node;
}

void rect_del(rect_table_t *rt, rect_key_t key)
{
    CALC_POSITION(rt, key);

    if (rt->ht[row] == NULL)
        return;
    if (rt->ht[row][col] == NULL)
        return;

    rect_node_t *prev, *n;
    prev = NULL;
    n = rt->ht[row][col];
    while (n != NULL) {
        if (rt->compare(n->key, key) == 0) {
            if (prev == NULL) {
                rt->ht[row][col] = n->next;
            } else {
                prev->next = n->next;
            }
            if (rt->free != NULL && n->val != NULL) {
                rt->free(n->val);
            }
            free(n);
            rt->used--;
            break;
        }
        prev = n;
        n = n->next;
    }
}



